/**
 * 4
3.8 排序算法
直接插入排序
1. 实现直接插入排序（升序），输出每趟排序结果。测试用例：[5,2,4,6,1,3]→过程：
第 1 趟：[2,5,4,6,1,3]
第 2 趟：[2,4,5,6,1,3]
... 最终：[1,2,3,4,5,6]
2. 对结构体数组排序：按学生成绩（int）升序，成绩相同则按姓名（字符串）字典序。测试用例：
Student s[] = {{"Bob", 85}, {"Alice", 90}, {"Bob", 80}}
排序后应为：{"Bob",80}, {"Bob",85}, {"Alice",90}
冒泡排序
1. 实现优化版冒泡排序（无交换时提前结束），统计排序趟数和交换次数。测试用例：
逆序数组 [6,5,4,3,2,1]→需 5 趟，15 次交换
已排序数组 [1,2,3,4,5]→仅 1 趟，0 次交换
2. 实现双向冒泡排序，对比普通冒泡在 "部分有序" 数组的效率：测试用例 [3,4,2,1,5,6]→双向冒泡需 2 趟，普通冒泡需 4 趟。
快速排序
1. 实现标准快速排序（首元素为基准），输出每轮分区结果。测试用例：[7,3,5,8,9,1,2,4,6]→首次分区后为 [6,3,5,4,2,1,7,9,8]。
2. 用三数取中法（首、尾、中值的中间值）优化快速排序，测试已排序数组 [1,2,3,4,5,6]→避免递归深度过深问题。
本套试题由曹婷老师根据元宇宙平台非凡就业班课程内容整理
选择排序
1. 实现简单选择排序，统计交换次数（对比冒泡排序的优势）。测试用例 [9,6,8,1,3,5]→仅需 3 次交换（冒泡需 11 次）。
2. 实现双向选择排序（每趟找最大和最小值），测试用例 [5,1,9,3,7,2,8,4,6]→普通选择需8 趟，双向选择需 5 趟。
 */

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

// 学生结构体定义
typedef struct {
    char name[20];
    int score;
} Student;

// 1. 直接插入排序（升序，输出每趟结果）
void insertionSort(int arr[], int n) {
    // 处理空数组或单元素数组，避免无效循环
    if (n <= 1) return;
    
    for (int i = 1; i < n; i++) {
        int temp = arr[i];
        int j = i - 1;
        // 移动比temp大的元素，为temp腾出位置
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
        
        // 输出当前趟结果，格式更清晰
        printf("第%d趟: [", i);
        for (int k = 0; k < n; k++) {
            printf("%d%s", arr[k], (k == n - 1) ? "]\n" : ", ");
        }
    }
}

// 2. 结构体数组排序（按成绩升序，成绩相同按姓名字典序）
void sortStudents(Student s[], int n) {
    if (n <= 1) return;
    
    for (int i = 1; i < n; i++) {
        Student temp = s[i];
        int j = i - 1;
        // 双重条件比较：先比成绩，成绩相同比姓名
        while (j >= 0) {
            bool needSwap = false;
            if (s[j].score > temp.score) {
                needSwap = true;
            } else if (s[j].score == temp.score) {
                // strcmp返回正数表示s[j].name字典序更大
                if (strcmp(s[j].name, temp.name) > 0) {
                    needSwap = true;
                }
            }
            
            if (needSwap) {
                s[j + 1] = s[j];
                j--;
            } else {
                break;
            }
        }
        s[j + 1] = temp;
    }
}

// 3. 优化版冒泡排序（统计趟数和交换次数，通过指针返回结果）
void bubbleSort(int arr[], int n, int* passes, int* swapCount) {
    // 初始化输出参数，避免未初始化的垃圾值
    *passes = 0;
    *swapCount = 0;
    if (n <= 1) return;
    
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        (*passes)++; // 每进入外层循环，计数一次趟数
        
        // 每趟将最大元素"冒泡"到末尾，已排序部分无需再比较
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                (*swapCount)++;
                swapped = true;
            }
        }
        
        if (!swapped) break; // 无交换说明数组已有序，提前退出
    }
}

// 4. 双向冒泡排序（返回总趟数）
int bidirectionalBubbleSort(int arr[], int n) {
    if (n <= 1) return 0;
    
    int left = 0, right = n - 1;
    int passes = 0;
    bool swapped;
    
    while (left < right) {
        swapped = false;
        passes++;
        // 从左到右：将大元素移到右侧
        for (int i = left; i < right; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = true;
            }
        }
        right--;
        if (!swapped) break;
        
        swapped = false;
        passes++;
        // 从右到左：将小元素移到左侧
        for (int i = right; i > left; i--) {
            if (arr[i] < arr[i - 1]) {
                int temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
                swapped = true;
            }
        }
        left++;
        if (!swapped) break;
    }
    return passes;
}

// 5. 快速排序（首元素为基准，输出每轮分区结果）
int partition(int arr[], int low, int high) {
    int pivot = arr[low]; // 基准元素（首元素）
    // 双指针交换：将比基准小的元素移到左侧，大的移到右侧
    while (low < high) {
        while (low < high && arr[high] >= pivot) high--;
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot) low++;
        arr[high] = arr[low];
    }
    arr[low] = pivot; // 将基准元素放到最终位置
    return low; // 返回基准元素索引
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotIdx = partition(arr, low, high);
        // 输出当前分区结果（从数组起始到high，匹配测试用例预期）
        printf("分区后: [");
        for (int i = 0; i <= high; i++) {
            printf("%d%s", arr[i], (i == high) ? "]\n" : ", ");
        }
        // 递归排序基准左侧和右侧子数组
        quickSort(arr, low, pivotIdx - 1);
        quickSort(arr, pivotIdx + 1, high);
    }
}

// 6. 三数取中法优化快速排序（解决有序数组递归深度问题）
int median3(int arr[], int low, int high) {
    int mid = low + (high - low) / 2; // 避免low+high溢出
    // 排序low、mid、high三个位置的元素，确保arr[low] <= arr[mid] <= arr[high]
    if (arr[low] > arr[mid]) {
        int temp = arr[low];
        arr[low] = arr[mid];
        arr[mid] = temp;
    }
    if (arr[low] > arr[high]) {
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }
    if (arr[mid] > arr[high]) {
        int temp = arr[mid];
        arr[mid] = arr[high];
        arr[high] = temp;
    }
    // 将中间值（arr[mid]）移到low+1位置，作为基准（隐藏基准，减少比较）
    int temp = arr[mid];
    arr[mid] = arr[low + 1];
    arr[low + 1] = temp;
    return arr[low + 1]; // 返回基准值
}

int partition3(int arr[], int low, int high) {
    int pivot = median3(arr, low, high);
    int i = low, j = high;
    // 从两侧向中间扫描，交换不符合基准的元素
    while (true) {
        while (arr[++i] < pivot); // 找到左侧第一个 >= 基准的元素
        while (arr[--j] > pivot); // 找到右侧第一个 <= 基准的元素
        if (i < j) {
            // 交换i和j位置的元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        } else {
            break; // i >= j时，分区完成
        }
    }
    // 将基准值移回最终位置（i处）
    int temp = arr[i];
    arr[i] = arr[low + 1];
    arr[low + 1] = temp;
    return i; // 返回基准元素索引
}

void quickSort3(int arr[], int low, int high) {
    if (low < high) {
        int pivotIdx = partition3(arr, low, high);
        quickSort3(arr, low, pivotIdx - 1);
        quickSort3(arr, pivotIdx + 1, high);
    }
}

// 7. 简单选择排序（统计交换次数，返回总交换数）
int selectionSort(int arr[], int n) {
    if (n <= 1) return 0;
    
    int swapCount = 0;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i; // 假设当前i是最小值索引
        // 找到[i, n-1]区间内的最小值索引
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        // 仅当最小值不在i位置时才交换，减少不必要操作
        if (minIdx != i) {
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
            swapCount++;
        }
    }
    return swapCount;
}

// 8. 双向选择排序（每趟找最大和最小值，返回总趟数）
int bidirectionalSelectionSort(int arr[], int n) {
    if (n <= 1) return 0;
    
    int left = 0, right = n - 1;
    int passes = 0;
    
    while (left < right) {
        passes++;
        int minIdx = left, maxIdx = right;
        // 一趟遍历同时找到最小值和最大值的索引
        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[minIdx]) {
                minIdx = i;
            }
            if (arr[i] > arr[maxIdx]) {
                maxIdx = i;
            }
        }
        // 1. 将最小值交换到left位置
        if (minIdx != left) {
            int temp = arr[left];
            arr[left] = arr[minIdx];
            arr[minIdx] = temp;
            // 若最大值在left位置，交换后最大值被移到minIdx，需更新maxIdx
            if (maxIdx == left) {
                maxIdx = minIdx;
            }
        }
        // 2. 将最大值交换到right位置
        if (maxIdx != right) {
            int temp = arr[right];
            arr[right] = arr[maxIdx];
            arr[maxIdx] = temp;
        }
        // 缩小排序区间
        left++;
        right--;
    }
    return passes;
}

//
// 排序算法测试（统一测试入口）
void testSort() {
    // 测试1：直接插入排序
    int arr1[] = {5, 2, 4, 6, 1, 3};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    printf("=== 直接插入排序测试 ===\n");
    insertionSort(arr1, n1);
    printf("\n");
    
    // 测试2：结构体数组排序
    Student s[] = {{"Bob", 85}, {"Alice", 90}, {"Bob", 80}};
    int n2 = sizeof(s) / sizeof(s[0]);
    printf("=== 结构体数组排序测试 ===\n");
    sortStudents(s, n2);
    printf("排序结果：");
    for (int i = 0; i < n2; i++) {
        printf("{%s, %d} ", s[i].name, s[i].score);
    }
    printf("\n\n");
    
    // 测试3：优化版冒泡排序
    int arr3[] = {6, 5, 4, 3, 2, 1}; // 逆序数组
    int arr4[] = {1, 2, 3, 4, 5};    // 已排序数组
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    int n4 = sizeof(arr4) / sizeof(arr4[0]);
    int passes, swapCount;
    
    printf("=== 优化版冒泡排序测试 ===\n");
    bubbleSort(arr3, n3, &passes, &swapCount);
    printf("逆序数组：%d趟，%d次交换（预期：5趟，15次）\n", passes, swapCount);
    
    bubbleSort(arr4, n4, &passes, &swapCount);
    printf("已排序数组：%d趟，%d次交换（预期：1趟，0次）\n\n", passes, swapCount);
    
    // 测试4：双向冒泡排序
    int arr5[] = {3, 4, 2, 1, 5, 6};
    int n5 = sizeof(arr5) / sizeof(arr5[0]);
    printf("=== 双向冒泡排序测试 ===\n");
    int biPasses = bidirectionalBubbleSort(arr5, n5);
    printf("总趟数：%d（预期：2趟）\n\n", biPasses);
    
    // 测试5：标准快速排序（首元素为基准）
    int arr6[] = {7, 3, 5, 8, 9, 1, 2, 4, 6};
    int n6 = sizeof(arr6) / sizeof(arr6[0]);
    printf("=== 标准快速排序测试 ===\n");
    quickSort(arr6, 0, n6 - 1); // 首次分区预期：[6,3,5,4,2,1,7,9,8]
    printf("\n");
    
    // 测试6：简单选择排序
    int arr7[] = {9, 6, 8, 1, 3, 5};
    int n7 = sizeof(arr7) / sizeof(arr7[0]);
    printf("=== 简单选择排序测试 ===\n");
    int selectSwap = selectionSort(arr7, n7);
    printf("交换次数：%d（预期：3次）\n\n", selectSwap);
    
    // 测试7：双向选择排序
    int arr8[] = {5, 1, 9, 3, 7, 2, 8, 4, 6};
    int n8 = sizeof(arr8) / sizeof(arr8[0]);
    printf("=== 双向选择排序测试 ===\n");
    int biSelectPasses = bidirectionalSelectionSort(arr8, n8);
    printf("总趟数：%d（预期：5趟）\n", biSelectPasses);
}

int main() {
    // 仅执行排序算法测试（删除未定义的testSearch调用）
    testSort();
    return 0;
}